package class17;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class KMP2 {

    public static int getIndexOf(String s1,String s2){
        if (s1==null||s2==null||s2.length()<1||s1.length()<s2.length())
            return -1;
        char[] str = s1.toCharArray();
        char[] match = s2.toCharArray();
        int x = 0;
        int y = 0;
        int[] next = getNextArray(match);
        while (x<str.length && y < match.length){
            if (str[x] == match[y]){
                x++;
                y++;
            }else if (next[y] == -1){
                x++;
            }else {
                y = next[y];
            }
        }
        return y == match.length ? x-y:-1;
    }

    public static int[] getNextArray(char[] match){
        if (match.length == 1)
            return new int[]{-1};
        int[] next = new int[match.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i<next.length){
            if (match[i-1] == match[cn]){
                next[i] = cn+1;
                i++;
                cn++;
            }else if (cn > 0){
                cn = next[cn];
            }else {
                next[i++] = 0;
            }

        }
        return next;
    }

    public static String getRandomString(int possibilities,int size){
        char[] ans = new char[(int)(Math.random() * size) +1];
        for (int i=0;i<ans.length;i++){
            ans[i] = (char)((int)(Math.random() * possibilities) + 'a');
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        int possibilities = 5;
        int strSize = 20;
        int matchSize = 5;
        int testTime = 500000;
        System.out.println("test begin!");
        for (int i=0;i<testTime;i++){
            String str = getRandomString(possibilities,strSize);
            String match = getRandomString(possibilities,matchSize);
            if (getIndexOf(str,match) != str.indexOf(match))
                System.out.println("Oops!");
        }
        System.out.println("test finish!");
    }
}
